#include <iostream>
#include <fstream>
#include <vector>
#include <cstdint>
#include <string>
#include <array>
#include <bitset>
#include <cstring>
#include <iomanip>
#include <emmintrin.h>

using Byte16 = std::array<uint8_t,16>;
using Byte20 = std::array<uint8_t,20>;
using Bit128 = std::bitset<128>;
using MDS16x16 = std::array<Byte16,16>;
// 通用模板函数，适用于任何支持范围的容器
template <typename Container>
void printHexBytes(const Container& bytes) {
    for (const auto& byte : bytes) {
        std::cout << std::hex << std::uppercase
                  << std::setw(2) << std::setfill('0')
                  << static_cast<int>(byte) << ' ';
    }
    std::cout << std::dec << std::endl; // 重置为十进制格式
}

class Cuckoo{
    
    public:
        explicit Cuckoo(size_t N){
            salts[0]  = 0x3F9A2C8D7E1B4A6F;
            salts[1]  = 0x8D3F2E1A9C7B4D5E;
            salts[2]  = 0x5A7C9D3F8B2E1A6D;
            this->N = N;
        }

        size_t hash(const Byte16& arr, int i) const {
                uint64_t part1 = 0;
                uint64_t part2 = 0;
                for (size_t i = 0; i < 8; ++i) {
                    part1 = (part1 << 8) | arr[i];
                    part2 = (part2 << 8) | arr[i + 8];
                }
                std::hash<uint64_t> hasher;
                return (hasher(part1) ^ (hasher(part2) << 1)^salts[i])%N;
        }
    
    private:
        uint64_t salts[3];// 用于hash计算的值
        size_t N;//模数

};

// 通用哈希 + 掩码 PRF，输入 128→输出 128，安全参数 ≥32
class UniversalHashMask128 {
private:
    // 编译期固定的“随机”常量（4 组 a_i、b_i，以及 16 字节 mask）
    // static constexpr 隐式 inline（C++17起），可直接在类内初始化【:contentReference[oaicite:0]{index=0}】【】
    inline static constexpr uint64_t a[4] = {
        0x21A1CE4D3F4895EFULL,
        0xD36163902D91908DULL,
        0xC43EAAF690B4E1E7ULL,
        0xC8D60DE5F82A1C29ULL
    };
    inline static constexpr uint64_t b[4] = {
        0x7C20BA20EF2F9895ULL,
        0x7DDE6BE1A1B6B5D6ULL,
        0x679BCAFB330C9BEFULL,
        0xD6030BB550350A0EULL
    };
    inline static constexpr uint8_t mask[16] = {
        0x5E, 0xAC, 0x33, 0x0A, 0xE9, 0x97, 0xFE, 0x33,
        0x13, 0x46, 0x87, 0x74, 0x4C, 0x1B, 0x8E, 0x22
    };

public:
    Byte16 operator()(const Byte16 &in) const {
        // 拆 128 位为 4×32 位小端整数
        uint32_t x[4];
        for(int i=0;i<4;i++){
            x[i] = uint32_t(in[4*i])
                 | uint32_t(in[4*i+1])<<8
                 | uint32_t(in[4*i+2])<<16
                 | uint32_t(in[4*i+3])<<24;
        }
        // 计算哈希并 XOR 掩码
        Byte16 out;
        for(int i=0;i<4;i++){
            uint64_t t = a[i] * uint64_t(x[i]) + b[i];  // 模 2^64 运算【:contentReference[oaicite:2]{index=2}】
            uint32_t hi = uint32_t(t >> 32);            // 取高 32 位
            for(int j=0;j<4;j++){
                out[4*i + j] = uint8_t((hi >> (8*j)) & 0xFF) ^ mask[4*i + j];
            }
        }
        return out;
    }
};

void concat_int_and_array(int32_t num, const Byte16& arr, Byte20& result) {

    // 方法2：memcpy（编译器优化，但依赖平台字节序）
    std::memcpy(&result[0], &num, sizeof(num));
    // 复制剩余的 16 字节
    std::copy(arr.begin(), arr.end(), result.begin() + 4);
}

// 辅助函数：单个字符转 4 位
uint8_t hex_char_to_byte(char c) {
    c = std::tolower(c);
    if (c >= '0' && c <= '9') return c - '0';
    if (c >= 'a' && c <= 'f') return 10 + (c - 'a');
    throw std::invalid_argument("Invalid hex character");
}

Byte16 hex_string_to_array(const std::string& hex_str) {
    if (hex_str.length() != 32) {
        throw std::invalid_argument("Hex string must be 32 characters (128 bits)");
    }
    Byte16 arr{};
    for (size_t i = 0; i < 32; i += 2) {
        uint8_t high = hex_char_to_byte(hex_str[i]);      // 高 4 位
        uint8_t low = hex_char_to_byte(hex_str[i + 1]);    // 低 4 位
        arr[i / 2] = (high << 4) | low;                   // 合并为 1 字节
    }
    return arr;
}

void xor_arrays(std::array<uint8_t, 16>& a, std::array<uint8_t, 16>& b){
    std::array<uint8_t, 16> result;
    for (size_t i = 0; i < 16; ++i) {
        b[i]^= a[i];
    }
    return;
}


void init_mark(const char* filename,std::vector<bool>& flags){
    // 以二进制模式打开
    std::ifstream fin(filename, std::ios::binary);
    if (!fin) {
        std::cerr << "无法打开文件: " << filename << "\n";
    }
    int cnt =0;
    // 读取循环
    while (true) {
        uint32_t value;
        // read() 不改变 value 大小端，只把底层字节拷进内存
        fin.read(reinterpret_cast<char*>(&value), sizeof(value));
        // gcount() 返回本次实际读取的字节数
        std::streamsize n = fin.gcount();
        if (n == 0) {
            // 文件已读完
            break;
        }
        flags[cnt] = (value > 0);
        cnt++;
    }
    fin.close();
}

void init_MatrixQ(const char* input_file,std::vector<Byte16>& MatrixQ,int totLine){

    std::ifstream fin(input_file, std::ios::binary);//二进制格式
    if(!fin.is_open()){
        std::cerr<<"can't open file::"<<input_file<<std::endl;
        return;
    }
    int cnt=0;
    std::array<uint8_t, 16> buffer;
    while (fin.read(reinterpret_cast<char*>(buffer.data()), buffer.size())) {
        // 读16字节
        if(cnt==totLine)
            break;
        MatrixQ.push_back(buffer);
        cnt++;
    }
    fin.close();
}
// Byte16 按位与（AND）
void byte16_and(const Byte16& a,  Byte16& b) {
    for (size_t i = 0; i < 16; ++i) {
       b[i] &= a[i] ;  // 逐字节按位与
    }
}

// Byte16 按位与（AND）
void byte16_xor(const Byte16& a,  Byte16& b) {
    for (size_t i = 0; i < 16; ++i) {
       b[i] ^= a[i] ;  // 逐字节按位异或
    }
}

inline uint64_t rotl64(uint64_t x, int8_t r) {
    return (x << r) | (x >> (64 - r));
}

inline uint64_t fmix64(uint64_t k) {
    k ^= k >> 33;
    k *= 0xff51afd7ed558ccd;
    k ^= k >> 33;
    k *= 0xc4ceb9fe1a85ec53;
    k ^= k >> 33;
    return k;
}

void pack_memcpy(uint64_t h1, uint64_t h2, Byte16& out) noexcept {
    std::memcpy(out.data(),     &h1, sizeof h1);     // 拷贝 h1 的 8 字节 :contentReference[oaicite:0]{index=0}  
    std::memcpy(out.data() + 8, &h2, sizeof h2);     // 拷贝 h2 的 8 字节 :contentReference[oaicite:1]{index=1}  
    return ;
}

void MurmurHash3_x64_128(const void* key, int len, uint32_t seed, Byte16& out) {
    const uint8_t* data = static_cast<const uint8_t*>(key);
    const int nblocks = len / 16;
    uint64_t h1 = seed;
    uint64_t h2 = seed;

    const uint64_t* blocks = reinterpret_cast<const uint64_t*>(data);
    for (int i = 0; i < nblocks; ++i) {
        uint64_t k1 = blocks[i * 2];
        uint64_t k2 = blocks[i * 2 + 1];

        k1 *= 0x87c37b91114253d5;
        k1 = rotl64(k1, 31);
        k1 *= 0x4cf5ad432745937f;
        h1 ^= k1;

        h1 = rotl64(h1, 27);
        h1 += h2;
        h1 = h1 * 5 + 0x52dce729;

        k2 *= 0x4cf5ad432745937f;
        k2 = rotl64(k2, 33);
        k2 *= 0x87c37b91114253d5;
        h2 ^= k2;

        h2 = rotl64(h2, 31);
        h2 += h1;
        h2 = h2 * 5 + 0x38495ab5;
    }

    const uint8_t* tail = data + nblocks * 16;
    uint64_t k1 = 0;
    uint64_t k2 = 0;
    switch (len & 15) {
        case 15: k2 ^= uint64_t(tail[14]) << 48;
        case 14: k2 ^= uint64_t(tail[13]) << 40;
        case 13: k2 ^= uint64_t(tail[12]) << 32;
        case 12: k2 ^= uint64_t(tail[11]) << 24;
        case 11: k2 ^= uint64_t(tail[10]) << 16;
        case 10: k2 ^= uint64_t(tail[9]) << 8;
        case 9:  k2 ^= uint64_t(tail[8]);
                 k2 *= 0x4cf5ad432745937f;
                 k2 = rotl64(k2, 33);
                 k2 *= 0x87c37b91114253d5;
                 h2 ^= k2;
        case 8:  k1 ^= uint64_t(tail[7]) << 56;
        case 7:  k1 ^= uint64_t(tail[6]) << 48;
        case 6:  k1 ^= uint64_t(tail[5]) << 40;
        case 5:  k1 ^= uint64_t(tail[4]) << 32;
        case 4:  k1 ^= uint64_t(tail[3]) << 24;
        case 3:  k1 ^= uint64_t(tail[2]) << 16;
        case 2:  k1 ^= uint64_t(tail[1]) << 8;
        case 1:  k1 ^= uint64_t(tail[0]);
                 k1 *= 0x87c37b91114253d5;
                 k1 = rotl64(k1, 31);
                 k1 *= 0x4cf5ad432745937f;
                 h1 ^= k1;
    }

    h1 ^= len;
    h2 ^= len;

    h1 += h2;
    h2 += h1;
    pack_memcpy(fmix64(h1),fmix64(h2),out);
}
// 布谷鸟hash->128
void hash20(const std::array<uint8_t, 20>& input_block,  std::array<uint8_t, 16>& hash_value) {
    MurmurHash3_x64_128(input_block.data(),20,0x12345678,hash_value);
}

int main(int argc,char* argv[]){
    
    if(argc!=7){
        std::cerr<<"params err\n";
        return 1;
    }
    int binsNum = std::stoi(argv[1]);//桶数
    std::string key_s = argv[2];//随机串s
    char* mark_file_name = argv[3];//虚位表
    char* q_file = argv[4];//矩阵Q
    char* data_name = argv[5]; //数据
    std::string output_path = argv[6];//输出路径
    std::string P_path = output_path+"/p.bin";//集合P
    std::string S_path = output_path+"/s.bin";//集合S
    size_t table_size = binsNum/3;
    Cuckoo cuckoo =Cuckoo(table_size);//布谷鸟hash
    std::vector<bool> flags(binsNum+3, false); //标记
    std::vector<Byte16>MatrixQ; //矩阵Q
    
    init_mark(mark_file_name,flags);//初始化虚值标记
    init_MatrixQ(q_file,MatrixQ,binsNum+3);//初始化矩阵Q
    
    // 以二进制模式打开
    std::ifstream fin(data_name, std::ios::binary);//读入数据
    std::ofstream fout_P(P_path, std::ios::binary);
    std::ofstream fout_S(S_path, std::ios::binary);
    if(!fin.is_open()||!fout_P.is_open()||!fout_S.is_open()){
        std::cerr<<"文件打开失败\n";
        return 1;
    }
    Byte16 buffer;
    Byte16 result;
    Byte16 tmp;
    Byte20 buffer_extend;
    Byte16 key = hex_string_to_array(key_s);
    size_t cnt=0;
    UniversalHashMask128 prf;
    while (fin.read(reinterpret_cast<char*>(buffer.data()), buffer.size()))
        {
           cnt++;
            for(int i=0;i<3;i++){
                auto pos = cuckoo.hash(buffer,i)+i*table_size;
                if(!flags[pos]) continue;//空hash不计算
                concat_int_and_array(i,buffer,buffer_extend);//i||x
             //   printHexBytes(buffer_extend);
                hash20(buffer_extend,tmp);//进行转换20->16
               // printHexBytes(tmp);  
                result= prf(tmp);//prf
                //printHexBytes(result);  
                byte16_and(key,result);//C*s
                // printHexBytes(result);
                byte16_xor(MatrixQ[pos],result);//q^(C*s)
               // printHexBytes(MatrixQ[pos]);
            //    std::cout<<pos<<"\n";
                //H()消除关联性
                fout_P.write(reinterpret_cast<char*>(result.data()), 16);//写到集合p
            }
            for(int i=0;i<3;i++){
                auto pos = binsNum+i;
                if(!flags[pos])continue;

                concat_int_and_array(3,buffer,buffer_extend);//3 ||x
                hash20(buffer_extend,tmp);//进行转换20->16
                result= prf(tmp);//prf
                byte16_and(key,result);//C*s
                byte16_xor(MatrixQ[pos],result);//q^(C*s)
                //H()消除关联性
                fout_S.write(reinterpret_cast<char*>(result.data()), 16);//写到集合s
            }
        }
    fin.close();
    fout_P.close();
    fout_S.close();
    std::cout<<cnt<<" elments have been processed!\n";
    return 0;

}